package net.tp.algo.sort;

/**
 *
 * <p>Counting sort.</p>
 *
 * <p>Counting sort is a stable sort running in $O(n+k)$ time.</p>
 *
 * <p>There are 3 ways of implementing counting sorts.</p>
 *
 * @author Trung Phan
 * @time $O(n)$
 * @space $O(n)$
 *
 */
public class CountingSort {

    public static void sort(int[] data, boolean asc) {

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < data.length; i++) {
            if (min > data[i]) min = data[i];
            if (max < data[i]) max = data[i];
        }

        int[] counts = new int[max-min+1];

        for (int i = 0; i < data.length; i++) {
            counts[data[i] - min]++;
        }

        if (asc) {
            for (int i = 1; i < counts.length; i++) {
                counts[i] += counts[i-1];
            }
        }
        else {
            for (int i = counts.length - 2; i >= 0; i--) {
                counts[i] += counts[i+1];
            }
        }

        int[] b = new int[data.length];
        for (int i = data.length - 1; i >= 0; i--) {
            b[--counts[data[i] - min]] = data[i];
        }

        for (int i = 0; i < data.length; i++) {
            data[i] = b[i];
        }
    }

}
